#include<stdio.h>
#include <stdlib.h>
#include<string.h>
#define MEM_SIZE 640//内存空间的大小
#define MAX_JOB 100//最多的作业数
//已经分配的内存链表 结构体
struct MEMLIST{
    int start;//分配的起始地址
    int size;//分配内存的大小
    int statu;//状态 0 free 1 busy  
    int id;//被分配到内存的job的id，未被分配为0
    struct MEMLIST* front;
    struct MEMLIST* next;
};
//作业 结构体
struct JOB{ 
    int id;//作业名
    int size;//需要的内存大小
    struct MEMLIST* memTo;//指向被分配的内存链表,方便后续释放内存处理
}job[MAX_JOB];

//创建一个结构体 记录链表的大小顺序，（因为内存链表本身顺序不能更改所以需要创建一个结构体来排序）
struct LISTORDER{
    int size;
    struct MEMLIST *linkToMem;
};
//对链表的内存大小LISTORDER快排
void QuickSort(struct LISTORDER array[], int low, int high) {
    int i = low; 
    int j = high;
    if(i >= j) {
        return;
    }

    struct LISTORDER temp = array[low];
    while(i != j) {
        while(array[j].size >= temp.size && i < j) {
            j--;
        }
	while(array[i].size <= temp.size && i < j) {
            i++;
        }
	if(i < j) {
			struct LISTORDER tmp=array[i];
			array[i]=array[j];
			array[j]=tmp;
        }
    }

    //将基准temp放于自己的位置，（第i个位置）
	struct LISTORDER tmp=array[low];
	array[low]=array[i];
	array[i]=tmp;
    QuickSort(array, low, i - 1);
    QuickSort(array, i + 1, high);
}

//MEMLIST内存分配链表初始化
void initMemlist(struct MEMLIST* memlist){
    memlist->start=0;
    memlist->size=0;
    memlist->statu=0;
    memlist->id=0;
    memlist->front=NULL;
    memlist->next=NULL;
}
//初始化
void initJob(struct JOB* job){
    job->id=0;//作业名
    job->size=0;//需要的内存大小
    job->memTo=NULL;//指向被分配的内存链表,方便后续释放内存处理
}
//显示内存链
void showMemList(struct MEMLIST* memlist){
    printf("\n\n======================内存情况============================\n");
    printf("==========================================================\n");
    printf("| 地址起始 | 地址结束 |   大小(KB) |  状态  |    作业号  |\n");
    struct MEMLIST* ml=memlist;
    while(ml!=NULL){
        printf("| %8d | %8d | %10d |",ml->start,ml->start+ml->size-1,ml->size);
        if(ml->statu==0)
            printf("  free  |");
        else
            printf("  busy  |");
            
        if(ml->id==0)
			printf("       null |\n");
		else
			printf(" %10d |\n",ml->id);
        
        ml=ml->next;
    }
    printf("==========================================================\n\n");
}
//分配内存
struct JOB* insertMem(struct MEMLIST* ml,int id,int size){
    //建立job对象
    struct JOB* job=(struct JOB*)malloc(sizeof(struct JOB));
    initJob(job);
    struct MEMLIST* memNext=(struct MEMLIST*)malloc(sizeof(struct MEMLIST));
    memNext->start=ml->start+size;
    memNext->size=ml->size-size;
    memNext->statu=0;
    memNext->next=NULL;
    memNext->id=0;
    //划分为使用的内存链表
    ml->size=size;
    ml->statu=1;//已分配
    ml->id =id;
    
    if(ml->next==NULL){//如果下一个内存块为空，则直接插入下面，断一个链
        memNext->front=ml;
        memNext->next=ml->next;
        ml->next=memNext;
    }else{//如果下一块不为空，则插入中间，断两个链
        memNext->next=ml->next;
        ml->next->front=memNext;
        ml->next=memNext;
        memNext->front=ml;
    }
    //设置作业
    job->id=id;
    job->size=size;
    job->memTo=ml;
    return job;
}

//best fit分配内存
struct JOB allocBF(int id,int size,struct MEMLIST* memlist){
    //建立job对象
    struct JOB* job=(struct JOB*)malloc(sizeof(struct JOB));
    initJob(job);
    
    // 未分配内存链表快的大小
    int memSize=0;
    struct MEMLIST *ml=memlist;
    while(ml!=NULL){
        if(ml->statu==0)
            memSize++;
        ml=ml->next;
    }

    //未分配的内存块创建链表顺序结构
    struct LISTORDER list[memSize];
    int t=0;
    ml=memlist;
    while(ml!=NULL){
        if(ml->statu==0){
            list[t].size=ml->size;
            list[t].linkToMem=ml;
            t++;
        }
        ml=ml->next;
    }
    
    //先排序
    QuickSort(list,0,memSize-1);

    //遍历内存大小 
    for(int i=0;i<memSize;i++){
        if(list[i].size>size){//如果要求分配的大小小于内存大小 就分配
            //分配
            ml=list[i].linkToMem;
            job=insertMem(ml,id,size);
            printf("成功为job %d 分配内存 %d KB ！\n",job->id,job->size);
            showMemList(memlist);
            return *job;
        }
    }
    printf("连续空闲内存不足！\n");
    return *job;
}
//firstfit分配内存
struct JOB allocFF(int id,int size,struct MEMLIST* memlist){
    //建立job对象
    struct JOB* job=(struct JOB*)malloc(sizeof(struct JOB));
    initJob(job);
    //遍历每个内存链表，用firstfit算法分配内存
    struct MEMLIST* ml=memlist;
    while(ml!=NULL){
        //如果内存链表中有一个内存大于等于所需要创建的job的size且该内存为free则分配
        if(ml->size>=size && ml->statu==0){
            //划分为未使用的内存链表
            job=insertMem(ml,id,size);//成功分配
            printf("成功为job %d 分配内存 %d KB ！\n",job->id,job->size);
            showMemList(memlist);
            return *job;
        }
        ml=ml->next;
    }
    printf("连续空闲内存不足！\n");
    return *job;
}
//free释放内存
void freeMem(struct JOB *job,struct MEMLIST *memlist){
	if(job->memTo==NULL){
		printf("无此作业！\n\n");
		return ;
	}
    //释放之前需要看看前一个和后一个的内存块是否使用
    int frontFlag=0,nextFlag=0;
    if(job->memTo->front==NULL || job->memTo->front->statu==1) frontFlag=1;
    if(job->memTo->next==NULL || job->memTo->next->statu==1) nextFlag=1;
    //如果上下都未使用则合并
    if(frontFlag==0 && nextFlag==0){
        job->memTo->front->size+=job->memTo->size+job->memTo->next->size;//大小为三者和
        job->memTo->front->next=job->memTo->next->next;//前一个直接指向第三个的下一个
        free(job->memTo->next);
        free(job->memTo);
    }else if(frontFlag==0 && nextFlag==1){//向上合并
        job->memTo->front->size+=job->memTo->size;//两者和
        job->memTo->front->next=job->memTo->next;//前者指向下一个的下一个
        free(job->memTo);
    }else if(frontFlag==1 && nextFlag==0){//向下合并
        job->memTo->size+=job->memTo->next->size;//两者和
        struct MEMLIST *next=job->memTo->next;
        job->memTo->next=job->memTo->next->next;//前者指向下一个的下一个
        job->memTo->id=0;    
        job->memTo->statu=0;
        job->memTo=NULL;
        job->id=0;
        job->size=0;
        free(next);//释放下一个防止前一个为NULL
    }else{//单独一块
        job->memTo->statu=0;
        job->memTo->id=0;
    }

    printf("成功释放 作业号： %d  大小： %d KB\n",job->id,job->size);
    job->memTo=NULL;
    job->id=0;
    job->size=0;
    showMemList(memlist);
}

//firstfit内存分配菜单 
void menuFF(struct MEMLIST *memlist){
    printf("======================================\n");
    printf("| 首次适应算法(FF)的动态分配方式模拟 |\n");
    printf("======================================\n");
    printf("|   1.      申请内存                 |\n");
    printf("|   2.      回收内存                 |\n");
    printf("|   3.    查看内存情况               |\n");
    printf("|   4.        退出                   |\n");
    printf("======================================\n\n");
    int index=0,id=0;
    printf("输入操作：");
    scanf("%d",&index);
    while(index!=5){
        switch (index){
        case 0:
            printf("\n======================================\n");
            printf("| 首次适应算法(FF)的动态分配方式模拟 |\n");
            printf("======================================\n");
            printf("|   1.      申请内存                 |\n");
            printf("|   2.      回收内存                 |\n");
            printf("|   3.    查看内存情况               |\n");
            printf("|   4.        退出                   |\n");
            printf("======================================\n\n");
            break;
        case 1:
            printf("************申请内存******************\n");
            int size;
            printf("输入作业号：");scanf("%d",&id);
		    if(id<=0){ printf("作业号必须大于0！\n");break;}
			if(job[id].memTo!=NULL){ printf("该作业号已被占用！\n");break;}
            printf("输入作业申请空间大小(KB)：");scanf("%d",&size);
            job[id]=allocFF(id,size,memlist);
            break;
        case 2:
            printf("************回收内存******************\n");
            int i;
            printf("输入需要回收的作业号：");scanf("%d",&i);
            freeMem(&job[i],memlist);
                break;
        case 3:
            printf("************查看内存情况******************\n");
            showMemList(memlist);
                break;

        default:
            break;
        }
        printf("输入操作(0:菜单  4:退出)：");
        scanf("%d",&index);
    }
    printf("****************Bye******************\n");
}
//bestfit内存分配菜单 
void menuBF(struct MEMLIST *memlist){
    printf("======================================\n");
    printf("| 最佳适应算法(BF)的动态分配方式模拟 |\n");
    printf("======================================\n");
    printf("|   1.      申请内存                 |\n");
    printf("|   2.      回收内存                 |\n");
    printf("|   3.    查看内存情况               |\n");
    printf("|   4.        退出                   |\n");
    printf("======================================\n\n");
    int index=0,id=0;
    printf("输入操作：");
    scanf("%d",&index);
    while(index!=5){
        switch (index){
        case 0:
            printf("\n======================================\n");
            printf("| 最佳适应算法(BF)的动态分配方式模拟 |\n");
            printf("======================================\n");
            printf("|   1.      申请内存                 |\n");
            printf("|   2.      回收内存                 |\n");
            printf("|   3.    查看内存情况               |\n");
            printf("|   4.        退出                   |\n");
            printf("======================================\n\n");
            break;
        case 1:
            printf("************申请内存******************\n");
            int size;
            printf("输入作业号：");scanf("%d",&id);
		    if(id<=0){ printf("作业号必须大于0！\n");break;}
			if(job[id].memTo!=NULL){ printf("该作业号已被占用！\n");break;}
            printf("输入作业申请空间大小(KB)：");scanf("%d",&size);
            job[id]=allocBF(id,size,memlist);
            break;
        case 2:
            printf("************回收内存******************\n");
            int i;
            printf("输入需要回收的作业号：");scanf("%d",&i);
            freeMem(&job[i],memlist);
                break;
        case 3:
            printf("************查看内存情况******************\n");
            showMemList(memlist);
                break;

        default:
            break;
        }
        printf("输入操作(0:菜单  4:退出)：");
        scanf("%d",&index);
    }
    printf("\n****************Bye******************\n");

}
int main(){
    //内存初始化
    struct MEMLIST memlist;
    initMemlist(&memlist);
    memlist.size=MEM_SIZE;


	int index=0;
    printf("1：最佳适应算法(BF)的动态分配方式模拟\n2: 首次适应算法(FF)的动态分配方式模拟\n选择分配的算法：\n");
    scanf("%d",&index);
    if(index==1)
		menuBF(&memlist);
	else
		menuFF(&memlist);
	
}